#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ID_LENGTH 20
#define MAX_NAME_LENGTH 50

typedef struct Student {
    char id[MAX_ID_LENGTH];
    char name[MAX_NAME_LENGTH];
    float score;
    struct Student* left;
    struct Student* right;
} Student;

Student* root = NULL;
int studentCount = 0;

// 函数声明
void printMenu();
Student* createStudent(char* id, char* name, float score);
Student* insertStudent(Student* node, char* id, char* name, float score);
Student* findStudent(Student* node, char* id);
Student* findMin(Student* node);
Student* deleteStudent(Student* node, char* id);
void inOrderTraversal(Student* node);
void freeTree(Student* node);
void addStudent();
void queryStudent();
void modifyScore();
void deleteStudentMenu();
void statScore();
void sortScore();
void saveAndExit();

void printMenu() {
    printf("===== 学生成绩管理系统 =====\n");
    printf("1. 添加学生\n");
    printf("2. 查询学生\n");
    printf("3. 修改成绩\n");
    printf("4. 删除学生\n");
    printf("5. 统计成绩\n");
    printf("6. 成绩排序\n");
    printf("7. 保存并退出\n");
    printf("==========================\n");
    printf("请输入选项：");
}

// 创建新学生节点
Student* createStudent(char* id, char* name, float score) {
    Student* newStudent = (Student*)malloc(sizeof(Student));
    strcpy(newStudent->id, id);
    strcpy(newStudent->name, name);
    newStudent->score = score;
    newStudent->left = NULL;
    newStudent->right = NULL;
    return newStudent;
}

// 插入学生到树中（按学号排序）
Student* insertStudent(Student* node, char* id, char* name, float score) {
    if (node == NULL) {
        studentCount++;
        return createStudent(id, name, score);
    }
    
    int cmp = strcmp(id, node->id);
    if (cmp < 0) {
        node->left = insertStudent(node->left, id, name, score);
    } else if (cmp > 0) {
        node->right = insertStudent(node->right, id, name, score);
    }
    
    return node;
}

// 查找学生
Student* findStudent(Student* node, char* id) {
    if (node == NULL) return NULL;
    
    int cmp = strcmp(id, node->id);
    if (cmp == 0) {
        return node;
    } else if (cmp < 0) {
        return findStudent(node->left, id);
    } else {
        return findStudent(node->right, id);
    }
}

// 找到最小节点
Student* findMin(Student* node) {
    while (node && node->left != NULL) {
        node = node->left;
    }
    return node;
}

// 删除学生
Student* deleteStudent(Student* node, char* id) {
    if (node == NULL) return NULL;
    
    int cmp = strcmp(id, node->id);
    if (cmp < 0) {
        node->left = deleteStudent(node->left, id);
    } else if (cmp > 0) {
        node->right = deleteStudent(node->right, id);
    } else {
        // 找到要删除的节点
        if (node->left == NULL) {
            Student* temp = node->right;
            free(node);
            studentCount--;
            return temp;
        } else if (node->right == NULL) {
            Student* temp = node->left;
            free(node);
            studentCount--;
            return temp;
        }
        
        // 有两个子节点的情况
        Student* temp = findMin(node->right);
        strcpy(node->id, temp->id);
        strcpy(node->name, temp->name);
        node->score = temp->score;
        node->right = deleteStudent(node->right, temp->id);
    }
    return node;
}

// 中序遍历（按学号顺序显示）
void inOrderTraversal(Student* node) {
    if (node != NULL) {
        inOrderTraversal(node->left);
        printf("%s\t%s\t%.1f\n", node->id, node->name, node->score);
        inOrderTraversal(node->right);
    }
}

// 释放树内存
void freeTree(Student* node) {
    if (node != NULL) {
        freeTree(node->left);
        freeTree(node->right);
        free(node);
    }
}

// 统计成绩的辅助函数
void statScoreHelper(Student* node, float* sum, float* max, float* min) {
    if (node != NULL) {
        *sum += node->score;
        if (node->score > *max) *max = node->score;
        if (node->score < *min) *min = node->score;
        statScoreHelper(node->left, sum, max, min);
        statScoreHelper(node->right, sum, max, min);
    }
}

void addStudent() {
    char id[MAX_ID_LENGTH];
    char name[MAX_NAME_LENGTH];
    float score;
    
    printf("请输入学号：");
    scanf("%s", id);
    printf("请输入姓名：");
    scanf("%s", name);
    printf("请输入成绩：");
    scanf("%f", &score);
    
    // 检查学号是否已存在
    if (findStudent(root, id) != NULL) {
        printf("该学号已存在！\n");
        return;
    }
    
    root = insertStudent(root, id, name, score);
    printf("学生添加成功！\n");
}

void queryStudent() {
    if (root == NULL) {
        printf("暂无学生信息！\n");
        return;
    }
    
    printf("学号\t姓名\t成绩\n");
    inOrderTraversal(root);
}

void modifyScore() {
    char id[MAX_ID_LENGTH];
    printf("请输入要修改成绩的学生学号：");
    scanf("%s", id);
    
    Student* student = findStudent(root, id);
    if (student != NULL) {
        printf("请输入新成绩：");
        scanf("%f", &student->score);
        printf("成绩修改成功！\n");
    } else {
        printf("未找到该学号的学生！\n");
    }
}

void deleteStudentMenu() {
    char id[MAX_ID_LENGTH];
    printf("请输入要删除的学生学号：");
    scanf("%s", id);
    
    Student* student = findStudent(root, id);
    if (student != NULL) {
        root = deleteStudent(root, id);
        printf("学生删除成功！\n");
    } else {
        printf("未找到该学号的学生！\n");
    }
}

void statScore() {
    if (root == NULL) {
        printf("暂无学生信息！\n");
        return;
    }
    
    float sum = 0, max = -1, min = 101;
    statScoreHelper(root, &sum, &max, &min);
    
    float avg = sum / studentCount;
    printf("平均分：%.2f，最高分：%.2f，最低分：%.2f\n", avg, max, min);
}

// 将树转换为数组进行排序
void treeToArray(Student* node, Student** array, int* index) {
    if (node != NULL) {
        treeToArray(node->left, array, index);
        array[(*index)++] = node;
        treeToArray(node->right, array, index);
    }
}

void sortScore() {
    if (root == NULL) {
        printf("暂无学生信息！\n");
        return;
    }
    
    // 将树转换为数组
    Student** studentArray = (Student**)malloc(studentCount * sizeof(Student*));
    int index = 0;
    treeToArray(root, studentArray, &index);
    
    // 按成绩排序（冒泡排序）
    for (int i = 0; i < studentCount - 1; i++) {
        for (int j = 0; j < studentCount - i - 1; j++) {
            if (studentArray[j]->score < studentArray[j + 1]->score) {
                Student* temp = studentArray[j];
                studentArray[j] = studentArray[j + 1];
                studentArray[j + 1] = temp;
            }
        }
    }
    
    printf("按成绩排序结果：\n");
    printf("学号\t姓名\t成绩\n");
    for (int i = 0; i < studentCount; i++) {
        printf("%s\t%s\t%.1f\n", studentArray[i]->id, studentArray[i]->name, studentArray[i]->score);
    }
    
    free(studentArray);
}

void saveAndExit() {
    printf("数据已保存，系统退出！\n");
    freeTree(root);
    root = NULL;
    exit(0);
}

int main() {
    int option;
    
    while (1) {
        printMenu();
        scanf("%d", &option);
        
        switch (option) {
            case 1:
                addStudent();
                break;
            case 2:
                queryStudent();
                break;
            case 3:
                modifyScore();
                break;
            case 4:
                deleteStudentMenu();
                break;
            case 5:
                statScore();
                break;
            case 6:
                sortScore();
                break;
            case 7:
                saveAndExit();
                break;
            default:
                printf("输入选项无效，请重新输入！\n");
        }
        
        // 清空输入缓冲区
        while (getchar() != '\n');
        printf("\n");
    }
    
    return 0;
}